\chapter{Вопрос № 28}

Теорема Лагрнажа об обращении - формулировка и доказательство. Явная формула для количества помеченных корневых деревьев.

\section{Теорема Лагранжа}

Пусть имеется 2 взаимообратные по отношению к композиции опф:
\[
	\begin{split}
		& f\left(x\right) = a_1 x + a_2 x^2 + a_3 x^3 + ... \\
		& g\left(x\right) = b_1 x + b_2 x^2 + b_3 x^3 + ... \\
		& a_1 \not= 1 \\
		& b_1 \not= 1
	\end{split}
\]
тогда $b_n$ равен коэффициенту при $x^{-1}$ в разложении функции $\frac{1}{n} \frac{1}{f^n\left(x\right)}$ в ряд Лорана с конечным числом отрицательных слагаемых:
\begin{equation}
	b_n = \left[x^n\right]g\left(x\right) = \frac{1}{n} \left[x^{-1}\right] \frac{1}{f^n\left(x\right)}
\end{equation}
где $\left[a\right]$ - в данном случае обозначает коэффициент при $a$.

\section{Применение к корневым помеченным деревьям}

Как известно функция перечисляющая корневые помеченные деревья и функция $f\left(x\right) = xe^{-x}$ взаимообратны относительно композиции, поэтому найдем коэффициент при $x^{-1}$ в разложении функции $\frac{e^{nx}}{nx^n}$:
\[
	\frac{1}{nx^n}\left(1 + nx + \frac{\left(nx\right)^2}{2!} + \frac{\left(nx\right)^3}{3!} + ...\right)
\]
получили ряд Лорана с конечным числом слогаемых с отрицательной степенью $x$, очевидно, что коэффициент при $x^{-1}$ имеет вид:
\[
	\hat t_n =\frac{n^{n-1}}{n\left(n-1\right)!} = \frac{n^{n-1}}{n!} \Rightarrow t_n = n^{n-1}
\]
а следовательно число помеченных деревьев (не корневых) получается равным:
\[
	\tilde t_n = \frac{t^n}{n} = n^{n-2}
\]
что и требовалось.

\section{Доказательство теоремы Лагранжа}

Распишем композицию $g\left(f\left(x\right)\right) = x$ подробнее:
\[
	b_1 f\left(x\right) + b_2 f^2\left(x\right) + b_3 f^3\left(x\right) + ... = x
\]
Продиффиринцируем все по $x$ и получим:
\[
	b_1 f'\left(x\right) + 2b_2 f\left(x\right)f'\left(x\right) + 3b_3f^2\left(x\right)f'\left(x\right) + ... = 1
\]
Теперь поделим все на $f^n\left(x\right)$:
\[
	b_1\frac{f'\left(x\right)}{f^n\left(x\right)} + 2b_2\frac{f'\left(x\right)}{f^{n-1}\left(x\right)} + 3b_3\frac{f'\left(x\right)}{f^{n-2}\left(x\right)} + ... = \frac{1}{f^n\left(x\right)}
\]
Теперь покажем что вклад в коэффициент при $x^{-1}$ может дать только член:
\[
	b_n \cdot n \frac{f'\left(x\right)}{f\left(x\right)}
\]
для всех остальнх коэффициент при $x^{-1}$ равен 0, для этого рассмотрим произвольное разложение функции в ряд Лорана:
\[
	h\left(x\right) = \frac{c_{-n}}{x^n} + \frac{c_{-n+1}}{x^{n-1}} + .. + \frac{c_{-1}}{x} + c_0 + c_1 x + c_2 x^2 + ...
\]
и его производную:
\[
	h'\left(x\right) = ... - \frac{c_{-1}}{x^2} + 0 + c_1 + 2c_2x + ...
\]
т. е. коэффициент при $x^{-1}$ у производной от произвольной функции равнен 0. Таким образом коэффициент может дать только слагаемое вида:
\[
	\frac{f'\left(x\right)}{f\left(x\right)}
\]
покажем, что в выражени выше этот коэффициент равен 1:
\[
	\frac{a_1 + 2 a_2 x + 3a_3 x^2 + ...}{a_1x + a_2x^2 + a_3x^3} = \frac{1}{x} \left[\frac{a_1 + 2 a_2x + 3a_3 x^2 + ...}{a_1 + a_2x + a_3 x^2 + ...}\right]
\]
чтобы выделить именно коэффициент при $x^{-1}$ находим значение этого отношения при $x = 0$, которое очевидно равно 1. А так как коэффициенты в левой и правой части при равных степенях $x$ должны совпадать, то коэффициент при $x^{-1}$ в разложении функции $\frac{1}{f^n\left(x\right)}$ равен $nb_n$, а поделив все на $n$ получаем теорему Лагранжа.
